package newcoder_exp.justPractise;
import java.util.*;

import org.junit.Test;

import utils.BracketUtils;

public class NC91 {
    /* 
        O(N^2)的动态规划据说都会超时，这种算法基本肯定超时
        而且会报莫名的SOF错误，就在这行：
            dfs(idx + 1, arr, lastMin, cur); //选择不要当前的元素
    */
    public class SolutionX {
        public int[] LIS (int[] arr) {
            if (arr == null || arr.length == 0) return new int[0];
            if (arr.length == 1) return arr;
            res = new PriorityQueue<>((l1, l2) -> {
                if (l1.size() != l2.size())
                    return l2.size() - l1.size();
                else {
                    for (int i = 0; i < l1.size(); i++) {
                        if (l1.get(i) != l2.get(i))
                            return l1.get(i) - l2.get(i);
                    }
                    return 0;
                }
            });
            dfs(0, arr, 0, new ArrayList<>());
            System.out.println(res);
            return res.peek().stream().mapToInt(Integer::valueOf).toArray();
        }

        Queue<List<Integer>> res;
        public void dfs(int idx, int[] arr, int lastMin, List<Integer> cur) {
            if (idx == arr.length) {
                res.offer(new ArrayList<>(cur));
                return;
            }
            dfs(idx + 1, arr, lastMin, cur); //选择不要当前的元素

            //选择要当前的元素
            if (arr[idx] > arr[lastMin]) {
                cur.add(arr[idx]);
                dfs(idx + 1, arr, idx, cur);
                cur.remove(cur.size() - 1);
            } else {
                dfs(idx + 1, arr, idx, new LinkedList<>(){{add(arr[idx]);}});
            }
        }
    }

    /* 
        超时,确实是正解
    */
    public class Solution1 {
        public int[] LIS (int[] arr) {
            if (arr == null || arr.length == 0) return new int[0];
            if (arr.length == 1) return arr;
            int[] f = new int[arr.length];
            //每个位置至少为1
            Arrays.fill(f, 1);
            int res = 1;
            for (int i = 1; i < arr.length; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[j] < arr[i]) {
                        f[i] = Math.max(f[j] + 1, f[i]);
                    }    
                }
                if (f[i] > res) {
                    res = f[i];
                }
            }
            int[] result = new int[res];
            Arrays.fill(result, Integer.MAX_VALUE);
            int idx = res - 1, last = f.length - 1;
            for (int i = res; i > 0; i--) {
                for (int j = last; j >= 0; j--) {
                    if (f[j] == i && arr[j] < result[idx]) {
                        result[idx] = arr[j];
                        last = j;
                    }
                }
                idx--;
            }
            return result;
        }
    }


    /* 
        避免第二轮的遍历
        使用help[f[i] - 1]记录长度的最小值
        又有一个问题：
        需要保证最大值不在最小值后面：如
            [2,1,5,3,6,4,8,9,7] 
        7和8对应的f都是4，但是算9的路径时只能取8
        必须要保证help[4 - 1 = 3] = 8而不是7

        可以在 ** 更新help时同时更新路径表示 ** 
    */

    /* 
        他的代码中：maxLen = f
        tail = help
    */
    public class Solution {
        public int[] LIS (int[] arr) {
            // write code here
    
            //tails[k]表示长度为k+1的最长递增子序列的末尾元素
            int[] tails = new int[arr.length];
            tails[0] = arr[0];
            int end = 0;
            //记录以当前元素为结尾的最长递增子序列的长度
            int[] maxLen = new int[arr.length];
            Arrays.fill(maxLen, 1);
    
            for (int i = 1; i < arr.length; i++) {
                int left = 0;
                int right = end + 1;
    
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (arr[i] > tails[mid]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                tails[left] = arr[i];
                if (left == end + 1) end++;
                if (left + 1 > maxLen[i]) maxLen[i] = left + 1;
            }
    
            int[] res = new int[end + 1];
            for (int i = arr.length - 1, j = res.length; j > 0; i--) {
                if (maxLen[i] == j) {
                    res[--j] = arr[i];
                }
            }
    
            return res;
        }
    }


    public class Solution2 {
        public int[] LIS (int[] arr) {
            if (arr == null || arr.length == 0) return new int[0];
            int len = arr.length;
            int[] f = new int[len];
            //各项初始化为1
            Arrays.fill(f, 1);
            int[] help = new int[len];
            help[0] = arr[0];
            int idx = 0; //help末尾元素下标
            int lo, hi;
            for (int i = 1; i < len; i++) {
                //将查找范围囊括当前遍历的元素
                lo = 0;
                hi = idx + 1;
                while (lo < hi) {
                    int mid = (hi + lo) / 2;
                    if (arr[i] > help[mid]) {
                        lo = mid + 1; //最终lo会来到hi的位置
                    } else {
                        hi = mid; //若arr[i]一直大于help[mid], hi保持idx靠后一格
                        //即新插入地元素位置
                    }
                }
                help[lo] = arr[i];
                if (lo == idx + 1) idx++;
                if (lo + 1 > f[i]) f[i] = lo + 1;
            }
            int[] res = new int[idx + 1];
            System.arraycopy(help, 0, res, 0, idx + 1);
            return res;
        }
    }

    @Test
    public void test() {
        // int[] nums = BracketUtils.to1DArray("[2,1,5,3,6,4,8,9,7]");
        int[] nums = BracketUtils.to1DArray("[1,2,8,6,4]");

        Solution2 s = new Solution2();
        int[] res = s.LIS(nums);
        System.out.println(Arrays.toString(res));
    }
}


/* 

            Map<Integer, Queue<Integer>> map = new HashMap<>();
                  if (map.containsKey(f[i])) {
                    map.get(f[i]).offer(arr[i]);
                } else {
                    Queue<Integer> queue = new PriorityQueue<>();
                    queue.offer(arr[i]);
                    map.put(f[i], queue);
                }
                res = Math.max(res, f[i]);


                result[i - 1] = map.get(i).peek();
*/